As a device for outputting a color image, a monitor and hard copy device such as a printer, and the like are available. The monitor reproduces colors by an RGB additive process, and the hard copy device reproduces colors by a CMYK subtractive process. In general, the color gamut of the monitor is broader than that of the hard copy device, and a color image displayed on the monitor cannot be faithfully reproduced by the hard copy device.
As a technique for attaining visual tint matching, gamut mapping is available. The following various methods are known as the gamut mapping:                (1) a method of linearly mapping the input color gamut within the output color gamut;        (2) a method of mapping only colors outside the output color gamut on the gamut boundary of the output color gamut; and        (3) a method of mapping colors outside the output color gamut on its high-saturation area to maintain a tone character.        
Method (1) does not lose the tone character since it maps linearly, but visually different colors may be reproduced. Method (2) is used when calorimetric color matching is required (e.g., for proof). However, two points outside the output color gamut may often be mapped at the same position on the boundary of the color gamut, thus losing the tone character and losing information of an image. Method (3) can minimize the sense of discomfort in terms of the human sense of vision, and is used to output photos and the like, since the tone character or an input image is maintained and original colors of a low-saturation area are preserved.
In method (2), in order to search for the location of the closest point in a device color gamut, color differences of all points are calculated, and a mapping destination is determined by interpolating (closer) points with smaller color differences. For this reason, as the number of points that express the device color gamut increases, mapping destination search requires longer time (described in, e.g., Japanese Patent Laid-Open No. 2002-094812 or USPAP 2002-031258).